
/* btnode.cpp: Functions for creating and managing binary tree. */

#include<string>
#include<iostream>
#include<cassert>
#include<sstream>
#include<cstdlib>
#include<osg/Timer>
#include<osgText/Font>
#include<osgText/Text>
#include<osg/ShapeDrawable>

#include "btnode.h"
#include "scenegraph.h"

#include<vector>

using namespace std;

/* Constructor: Binary tree node. */
BinaryTreeNode::BinaryTreeNode(double key_value)
{
	key = key_value;
	left = NULL;
	right = NULL;
	parent = NULL;
	height = 0;

	x = 0.0, z = 0.0;
	color = RED;
}

/* Simple binary tree. Insert operation. 
 * Based on pseudo-code in text book "Algorithms" Rivest, Cormen.
 * TODO: Simplify
 */
void BinaryTreeNode::insert(BinaryTreeNode*& root_node, BinaryTreeNode * nodez)
{
	BinaryTreeNode * nodey, * nodex;

	nodey = NULL;
	nodex = root_node;
	while(nodex != NULL)
	{
		nodey = nodex;
		if(nodez->key < nodex->key)
			nodex = nodex->left;
		else	
			nodex = nodex->right;
	}
	nodez->parent = nodey;
	if(nodey == NULL)
			root_node = nodez;
	else {
		if(nodez->key < nodey->key)
			nodey->left = nodez;
		else
			nodey->right = nodez;
	}
	nodez->left = NULL;
	nodez->right = NULL;
	nodez->color = RED;
}

/* Red Black tree related functions.
 * rb_insert, rb_insert_fixup, left_rotate, right_rotate.
 * Based on pseudo-code in text book "Algorithms" Rivest, Cormen.
 * */
void BinaryTreeNode::rb_insert(BinaryTreeNode*& root_node, BinaryTreeNode * nodez)
{
	insert(root_node, nodez);
	rb_insert_fixup(root_node, nodez);
}

void BinaryTreeNode::left_rotate(BinaryTreeNode*& t, BinaryTreeNode * nodex)
{
	BinaryTreeNode * nodey;

	nodey = nodex->right;
	nodex->right = nodey->left;

	if(nodey->left != NULL)
		nodey->left->parent = nodex;

	nodey->parent = nodex->parent;
	if(nodex->parent == NULL)
		t = nodey;
	else { 
		if (nodex == nodex->parent->left)
			nodex->parent->left = nodey;
		else
			nodex->parent->right = nodey;
	}
	nodey->left = nodex;
	nodex->parent = nodey;
}

void BinaryTreeNode::right_rotate(BinaryTreeNode*& t, BinaryTreeNode * nodex)
{
	BinaryTreeNode * nodey;

	nodey = nodex->left;
	nodex->left = nodey->right;

	if(nodey->right != NULL)
		nodey->right->parent = nodex;
	nodey->parent = nodex->parent;
	if(nodex->parent == NULL)
		t = nodey;
	else { 
		if (nodex == nodex->parent->left)
			nodex->parent->left = nodey;
		else
			nodex->parent->right = nodey;
	}
			nodey->right = nodex;
	nodex->parent = nodey;
}

/* + Description: Insert new node in the binary tree. 
 * Maintain binary tree property. 
 * + Arguments: Pointer to tree node object.
 * */

void BinaryTreeNode::rb_insert_fixup(BinaryTreeNode*& t, BinaryTreeNode * nodez)
{
	BinaryTreeNode * nodey;

	while(nodez->parent != NULL && nodez->parent->color == RED)
	{
		if(nodez->parent == nodez->parent->parent->left) {

			/* z's parent is LEFT child */
			nodey = nodez->parent->parent->right;
			if(nodey != NULL && nodey->color == RED) {
				/* z's uncle is RED. */
				nodez->parent->color = BLACK;
				nodey->color = BLACK;
				nodez->parent->parent->color = RED;
				nodez = nodez->parent->parent;

			} else {
				/* z's uncle is BLACK. */
				if(nodez == nodez->parent->right) {
					/* z is RIGHT child. */
					nodez = nodez->parent;
					left_rotate(t, nodez);
				}
				nodez->parent->color = BLACK;
				nodez->parent->parent->color = RED;
				right_rotate(t, nodez->parent->parent);
			}


		} else {

			/* z's parent is RIGHT child */
			nodey = nodez->parent->parent->left;
			if(nodey != NULL && nodey->color == RED) {
				/* z's uncle is RED. */
				nodez->parent->color = BLACK;
				nodey->color = BLACK;
				nodez->parent->parent->color = RED;
				nodez = nodez->parent->parent;

			} else {
				/* z's uncle is BLACK. */
				if(nodez == nodez->parent->left) {
					/* z is LEFT child. */
					nodez = nodez->parent;
					right_rotate(t, nodez);
				}
				nodez->parent->color = BLACK;
				nodez->parent->parent->color = RED;
				left_rotate(t, nodez->parent->parent);
			}
		}
	}
	t->color = BLACK;
}


/* + Description: Draw this node at correct place in the binary tree.
* This is achieved by creating scenegraph. 
*
* Each node will be denoted by a circle.
* Key value will be drawn inside the circle.
* The node circle will be connected to parent node's circle.
*
* + Precondition: Should be called after node is added to the binary tree. 
* */
#define RAD 1.0
void BinaryTreeNode::tree_draw(osg::ref_ptr<osg::Geode>& geode)
{
	this->set_position();
	this->draw(geode);	

	if(this->left != NULL)
			this->left->tree_draw(geode);

	if(this->right != NULL)
			this->right->tree_draw(geode);
}

/* Set position using parent node pointer. */
void BinaryTreeNode::set_position(void)
{
	if(this->parent != NULL)
		this->height = parent->height + 1; 
	else height = 0;

	if(this->parent == NULL) {
		x = 0.0; 
		z = 0.0;

	} else if(this == parent->left) {
		x = parent->x - 6.0/height;
		z = parent->z - 3.0;

	} else {
		x = parent->x + 6.0/height;
		z = parent->z - 3.0;
	}
}

/* Actual drawing for binary tree node. It consists:
 * A circle, line from parent to the circle, and label.
 * */
void BinaryTreeNode::draw(osg::ref_ptr<osg::Geode>& geode)
{
	/* Draw this node and label. */
	this->shape = create_circle(x, z, RAD);
	geode->addDrawable(this->shape.get() );

	/* Connect this node with its parent. */
	if(parent != NULL)
    	geode->addDrawable(create_line(x, z+RAD, parent->x, parent->z).get() );

	this->apply_color();
	this->draw_label(geode);
}

// Utility function
osg::Vec4 get_color_vec(NodeColor color)
{
	osg::Vec4 vec;
	if(color == WHITE)
		vec = osg::Vec4(1.0, 1.0, 1.0, 1.0);
	else if(color == BLACK)
		vec = osg::Vec4(0.0, 0.0, 0.0, 1.0);
	else if(color == RED)
		vec = osg::Vec4(1.0, 0.0, 0.0, 1.0);
	else if(color == GREEN)
		vec = osg::Vec4(0.0, 1.0, 0.0, 1.0);
	else if(color == BLUE)
		vec = osg::Vec4(0.0, 0.0, 1.0, 1.0);
	else
		vec = osg::Vec4(0.0, 0.0, 0.0, 1.0);
	return vec;
}


/* Draw label for this tree node. The text will be value/key of 
 * this tree node. */
void BinaryTreeNode::draw_label(osg::ref_ptr<osg::Geode>& geode)
{
	osg::ref_ptr<osgText::Font> font = osgText::readFontFile("fonts/arial.ttf");
	this->label = new osgText::Text;

	/* Convert value of the key to string. */
	stringstream out;
	out << this->key;

	label->setFont(font.get());
	label->setFontResolution(128, 128);
	label->setText(osgText::String(out.str()));

	label->setPosition(osg::Vec3(x, -0.1, z));

	label->setAxisAlignment(osgText::Text::SCREEN);
	label->setAlignment(osgText::Text::CENTER_CENTER);
	label->setCharacterSize(0.6);
	// Label color is always white
	label->setColor(osg::Vec4(1.0, 1.0, 1.0, 1.0));
	geode->addDrawable(label.get());
}

/* Apply color to shape and label drawn in the scenegraph. */
void BinaryTreeNode::apply_color()
{
	this->color_vec = get_color_vec(this->color);
	osg::ref_ptr<osg::Vec4Array> c = new osg::Vec4Array;
	c->push_back(this->color_vec);

	shape->setColorBinding(osg::Geometry::BIND_OVERALL);
	shape->setColorArray(c.get());
}

/* Print for debugging. */
void BinaryTreeNode::print_tree(void)
{
	cout << "key = " << key << endl;
	if(this->left != NULL)
		this->left->print_tree();
	if(this->right != NULL)
		this->right->print_tree();
}


/* Destructor. */
BinaryTreeNode::~BinaryTreeNode()
{

}

